插入区间

[编程题]插入区间

热度指数：1741 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无重叠的，按照区间起点升序排列的区间列表，在列表中插入一个新区间，如果有原区间有重合，则合并，请返回插入后的区间列表。

数据范围：区间列表长度满足 $0 \le n \le 10^4 \$ ，区间的左右端点满足 $0 \le l,r \le 10^5 \$

示例1

输入

[[2,5],[6,11]],[5,6]

输出

[[2,11]]

示例2

输入

[],[2,5]

输出

[[2,5]]

算法知识视频讲解

Python 3

liangzhengjie

class Solution:
    def insertInterval(self , Intervals: List[Interval], newInterval: Interval) -> List[Interval]:
        # write code here
        if len(Intervals) == 0:
            return [newInterval]

        res  = []
        res.append(Intervals[0])

        selected = False
        for i in range(len(Intervals)):
            if not selected:
                if self.is_interval_intersect(newInterval, res[-1]):
                    res[-1].start = min(res[-1].start, newInterval.start)
                    res[-1].end = max(res[-1].end, newInterval.end)
                    selected = True

            if self.is_interval_intersect(res[-1], Intervals[i]):
                res[-1].start = min(res[-1].start, Intervals[i].start)
                res[-1].end = max(res[-1].end, Intervals[i].end)
            else:
                res.append(Intervals[i])

        if not selected:
            res.append(newInterval)

        return res

    def is_interval_intersect(self, i1, i2):
        a1,b1 = i1.start,i1.end
        a2,b2 = i2.start,i2.end

        if a1 <= a2 <= b1&nbs***bsp;a1 <= b2 <= b1&nbs***bsp;a2 <= a1 <= b2:
            return True
        else:
            return False

发表于 2024-04-01 22:45:05 回复(0)